package LeetCode.exercise;

public class LC188 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp1 = new int[n][k+1], dp2 = new int[n][k+1];
        dp1[0][0] = -prices[0];
        for(int i = 1; i <= k; i++){
            dp1[0][i] = Integer.MIN_VALUE;
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                dp1[i][j] = Math.max(dp1[i-1][j], dp2[i-1][j] - prices[i]);
                dp2[i][j] = dp2[i-1][j];
                if(j - 1 >= 0){
                    dp2[i][j] = Math.max(dp2[i][j], dp1[i-1][j-1] + prices[i]);
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i <= k; i++){
            if(dp2[n-1][i] > max){
                max = dp2[n-1][i];
            }
        }
        return max;
    }
}
